//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 
//
// 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 
//
// 
//
// 示例 1: 
//
// 
//输入: num1 = "2", num2 = "3"
//输出: "6" 
//
// 示例 2: 
//
// 
//输入: num1 = "123", num2 = "456"
//输出: "56088" 
//
// 
//
// 提示： 
//
// 
// 1 <= num1.length, num2.length <= 200 
// num1 和 num2 只能由数字组成。 
// num1 和 num2 都不包含任何前导零，除了数字0本身。 
// 
// Related Topics 数学 字符串 模拟 👍 950 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * [P43]_字符串相乘
 * @author cjl
 * @date 2022-06-11 16:56:35
 */
public class P43_MultiplyStrings{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P43_MultiplyStrings().new Solution();
          System.out.println("args = " + solution.multiply("123", "45"));
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          /**
           * 解题思路：第i位和第j位逐位相乘,放入[i+j+1]位第数组中
           * @param num1
           * @param num2
           * @return
           */
//    public String multiply(String num1, String num2) {
//        if("0".equals(num1) || "0".equals(num2)){
//            return "0";
//        }
//        int[] resArray = new int[num1.length() + num2.length()];
//        for(int i = num1.length() -1; i >= 0; i--){
//            //1,2,3
//            for(int j = num2.length() -1 ; j >=0; j--){
//                ///4,5,6
//                resArray[i + j + 1 ] += (num2.charAt(j) - '0') * (num1.charAt(i) - '0');
//            }
//        }
//        StringBuilder sb = new StringBuilder();
//        int jw = 0; //进位
//        for(int i = resArray.length -1; i >= 0 ; i--){
//            int tmp = (resArray[i] + jw) % 10; // 当前位值
//            jw = (resArray[i] + jw) / 10; // 进位值
//            resArray[i] = tmp;
//        }
//        for(int i = 0; i < resArray.length ; i++){
//            if(i == 0 && resArray[0] == 0){
//                continue;
//            }
//            sb.append(resArray[i]);
//        }
//        return sb.toString();
//    }

          public String multiply(String num1, String num2) {
              if(num1.equals("0") || num2.equals("0")){
                  return "0";
              }
              List<Long> resArray = new ArrayList<>(); //暂存结果
              char[] array1 = num1.toCharArray();
              char[] array2 = num2.toCharArray();
              //第i位和第j位相乘，补0后直接相加；
              for(int i = array1.length-1 ; i >= 0; i--){
                  for(int j = array2.length-1; j >= 0; j--){
                      long tmp = (long)((array1[i]-'0') * (array2[j] - '0') *
                              Math.pow(10, (array1.length -1 - i + array2.length - 1 - j)));
                      resArray.add(tmp);
                  }
              }
              long result = resArray.stream().mapToLong(Long::longValue).sum();
              return String.valueOf(result);
          }
}
//leetcode submit region end(Prohibit modification and deletion)

  }